With the advent of EDA, design of complex hardware systems no longer begins with a hardware circuit diagram. Instead, it begins with a software program that describes the functionality of the hardware system. FIG. 1 provides one general representation of the EDA process. At 110, a software program may be written in hardware description language (HDL) (e.g., VHDL and Verilog) that defines an algorithm to be performed with limited implementation details. Then at 120, designers may use logic and physical synthesis tools to ultimately generate a netlist which includes a list of components in the circuit design and the interconnections between the components. At this synthesis level, designers may generate alternate architectures for the circuit design by modifying constraints (such as clock period, number and type of data path elements, and desired number of clock cycles). Then at 130, the netlist and information about the layout of the circuit design may be used to determine the optimal placement of the various components of the circuit design and their routing. Finally, at 140, the physical circuit may be created.
One type of electronic device on which circuits may be created is referred to as a programmable logic device (PLDs). PLDs provide system designers with the ability to quickly create custom logic functions. PLDs may also be reprogrammable, meaning that the logic configuration can be modified after the initial programming. Types of PLDs may include but are not limited to FPGA (Field-Programmable Gate Array), PLAs (programmable logic arrays), PAL (Programmable Array Logic) and CPLDs (complex PLDs). A PLD typically includes an array of individually programmable logic units each of which is changeably interconnected to other programmable logic units on the device and to input/output (I/O) pins. For example, the FPGAs may be comprised of pre-defined programmable logic cells (PLCs). Each of these logic cells may further comprise a pre-defined set of programmable and nonprogrammable components (e.g., gates, look up tables (LUTs), registers etc.). Multiple such logic cells may be replicated throughout the device and the components within may be programmed to implement a circuit design. Within a layout of a FPGA device, the logic cell may be the most basic unit represented and the components within are pre-determined to the extent that they are typically the same across all the logic cells. Besides such basic layout units, the device layout may contain other layout units that represent other device components such as a memory layout unit that represents memory components of a device. However, among PLDs all other components of a device (e.g., memory) may be uniformly represented with respect to each other. For example, in an FPGA the layout units representing memory components commonly occupy an area of the device layout which may be represented as some multiple of the area occupied by a basic layout unit of the FPGA, which is the logic cell layout unit.
Other devices such as application specific integrated circuits (ASICs) may also be programmed to implement a custom circuit. For example, the gate array type of ASICs are comprised of multiple pre-defined sets of programmable gate arrays that may be programmed (much like a PLD) to implement a particular circuit design. In such devices, much like an FPGA, the basic unit of the layout, which in this case is a gate array, may be replicated multiple times through out the device. In general, all other components of the device may be typically represented as occupying an area which is a multiple of ten area occupied by of the basic layout unit.
When a designer uses EDA tools to model the implementation of a function on a device (e.g., FPGA, gate array ASIC), not all the available components of a device may be used for a particular implementation. Thus, it may be desirable for a designer to be able to see a graphical representation of the device layout in order to optimize the placement and routing of the circuit. For example, a designer may wish to define an area of a device layout and formulate a query requesting information about the device components within that area. A designer may also wish to know the type and number of unused components within an area. He or she may also wish to interactively change the placement and routing on a particular implementation based on the results of such a query or upon seeing a graphical representation of the device layout in its current form. This optimization process may also be automated through an algorithm that queries information regarding a device layout and automatically improves the circuit design by altering placement, routing and other variables. For these and other reasons it may be desirable to search a device layout to determine information such as what components are still available for programming.
Searching a device layout to determine information may be complicated by the fact that each device might have large numbers of components located within the areas to be searched. Furthermore, besides the basic layout units, the device layout may show other structures such as memory cells, CPUs etc., which may or may not conform to a physical representation that is uniform with the basic layout units.
Several known search methods have attempted to simplify the search process by dividing the layout area into conceptual sections or sub-areas and searching the individual sections to identify individual layout units (e.g., the basic logic cell, memory cells structure, etc.) and any components contained within. One such known division method is known as the binning structure. The binning structure method divides all device layouts, regardless of their physical dimensions, to some fixed number of sub-areas in the horizontal and vertical directions. Such a method may not be flexible enough to uniquely identify all layout units. For example, the size of a sub-area cannot be changed in some cases to accommodate the layout units of different physical sizes. Thus, some of the larger layout units (e.g., memory or CPU) may be represented within or straddle multiple sub-areas of the layout. This complicates the search process because the conflicts between multiple overlapping sub-areas representing the same unit on the layout has to be resolved somehow. Other known conventional methods of subdividing the physical layout of a device such as the HV-VH (horizontal-vertical and vertical-horizontal) and quadruple division all suffer from similar inflexibility. Thus, there is a need for a more effective method of subdividing the physical layout of a device.